// 树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；
//     常见的 DFS ： 先序遍历、中序遍历、后序遍历；
//     常见的 BFS ： 层序遍历（即按层遍历）。

//树的深度 = max(maxDepth(root.left), maxDepth(root.right)) + 1

// int maxDepth(struct TreeNode* root){
//     return root?(fmax(maxDepth(root->left),maxDepth(root->right))+1):0;
// }


int maxDepth(struct TreeNode* root){
    int l, r, max = 0;
    if (root == NULL) return 0;
    l = maxDepth(root->left);
    r = maxDepth(root->right);
    max = (l>r)? l:r;
    return (max+1);
}


// 是否为平衡二叉树，左右节点深度差不超过1
bool isBalanced(struct TreeNode* root){
    int ret;
    if (root == NULL) return true;
    if (abs(maxDepth(root->left) - maxDepth(root->right)) <= 1) {
        ret = isBalanced(root->left) && isBalanced(root->right);
        return ret;
    }   
    else return false;
}